class Solution {
public:
    vector<string> ans;
    vector<int> temp;
    void dfs(int k, string& s, vector<int>& temp){
        if(temp.size() == 4 && k==s.size()){
            ans.emplace_back(to_string(temp[0])+'.'+
                                to_string(temp[1])+'.'+
                                to_string(temp[2])+'.'+
                                to_string(temp[3]));
            return ;
        }
        else if(temp.size() > 4) return;
        for(int i=1; i<=3; ++i){
            if(k+i > s.size()) break;
            if(i>1 && s[k]=='0') break;
            int t = stoi(s.substr(k, i));
            if(t<0 || t>255) continue;
            temp.push_back(t);
            dfs(k+i, s, temp);
            temp.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        dfs(0, s, temp);
        return ans;
    }
};